Developer CD Series 1992 June: ROMin Holiday

home *** CD-ROM | disk | FTP | other *** search

/ Developer CD Series 1992 June: ROMin Holiday / ADC Developer CD (1992-06) (''ROMin Holiday'')_iso / Developer Connection - 06-1992.iso / Development Platforms / LISP Related / U. Mass AI & LISP Tools / MODULES / RULES / Rules.lisp < prev

Wrap

Text File | 1990-06-24 | 43.6 KB | 947 lines | [TEXT/CCL ]

; (c) Copyright 1990 by University of Massachusetts. All rights reserved. ; This software was conceived, designed, and written by Dan Suthers ; while supported by the National Science Foundation under grant number ; MDR 8751362, and by a fellowship from Apple Computer, Inc., Cupertino, ; CA. Partial support was also received from the Office of Naval Research ; under a University Research Initiative Grant, contract N00014-86-K-0764. ; Mr. Suthers created this software under his own initiative while in an ; academic relationship with the University of Massachusetts. The above ; copyright notice was a condition placed by University lawyers on approval ; of distribution of this software by Apple Computer, and is not meant to ; imply that this software was created in an employment or "work for hire" ; relationship between the University and Mr. Suthers. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; File: RULES.lisp ; Author: Dan Suthers ; Created: 19-Oct-88 21:57:32 ; Modified: 22-Jun-90 02:16:28 (Dan Suthers) ; Language: Common Lisp ; Package: RULE ; ; Description: Loads a rule-based reasoner built on the pattern matching ; facilities of DNET. Supports forward and backward reasoning. ; ; This is just a top-level REQUIRE file for the entire rules ; system. You may load subportions as noted below. This file ; also contains user and programmer documentation. ; ; (c) Copyright 1988, by Daniel D. Suthers ; Department of Computer and Information Science ; University of Massachusetts ; Amherst, Massachusetts 01003 ; ; This software was conceived, designed, and written by Dan Suthers ; while supported by the National Science Foundation under grant number ; MDR 8751362, and by a fellowship from Apple Computer, Inc., Cupertino, ; CA. Partial support was also received from the Office of Naval Research ; under a University Research Initiative Grant, contract N00014-86-K-0764. ; I wish to acknowledge the generous support of Beverly Woolf, who obtained ; the above grants and encouraged me to pursue my own research interests in ; her lab. This work would not have been possible without the resources and ; stimulating environment of the Computer and Information Science department. ; ; Permission to use, modify, and distribute this software is granted subject ; to the following restrictions and understandings: ; 1. The file header, including this notice, shall be retained, and may be ; extended to include documentation of modifications to the software. ; 2. This material is for nonprofit educational and research purposes only. ; Users are requested, but not required, to inform Mr. Suthers of any ; noteworthy uses of this software. ; 3. Mr. Suthers and the University of Massachusetts make no warrantee or ; representation that the operation of this software will be error free, ; and are under no obligation to provide any services. ; 4. Any user of such software agrees to indemnify and hold harmless Mr. ; Suthers and the University of Massachusetts from all claims arising ; out of the use or misuse of this software, or arising out of any ; accident, injury, or damage whatsoever, and from all costs, counsel ; fees, and liabilities incurred in or about any such claim, action, or ; proceeding brought thereon. ; 5. All materials and reports developed as a consequence of the use of ; this software shall duly acknowledge such use, in accordance with ; the usual standards of acknowledging credit in academic research. ; ; Status: Mostly done. ; ; Changes: See other files. ; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; ;;; USER'S DOCUMENTATION ;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; #| The most up-to-date documentation is to be found associated with the definitions of the relevant SM object types (RULE and TRACE-NODE :comments); and associated with the function definitions. Here I provide some examples and guidelines. Variables in rules are the same as DNET variables, namely, symbols in the ? package. They are declared with (dnet:defvariable <name>). Special forms recognized in the rules include: (:AND <C1> ... <Cn>) - If in the consequent, this is only for convienence, and the rule is parsed into multiple rules. If in the antecedent, forward and backward chaining tries to process each of <C1> ... <Cn> in the order given. Any :AND not at top level in the consequent results in factoring of the consequent. This is logical conjunction. SUPPORT doesn't short-circuit evaluation when :record-failure is T. This allows applications to identify "near misses", etc. (:SEQ <C1> .. <Cn>) - Like :AND, but is always short-circuited on failure, even when :record-failure is T. (SEQuential conjunction.) (:OR <f1> ... <fn>) - for convienence in the antecedent only. The rule will be stored as multiple rules resulting from factoring out :OR. Ignored in the consequent. (:LISP <expr1> ... <exprN>) - Variables in the current bindings list are lambda-bound, and the expressions are evaluated, as in PROGV, the last value being returned. When the :LISP form occurs in the antecedent, the result of evaluation is used to determine success (whether forward or back chaining). It is useful in the consequent when side effects are desired in forward chaining, and to insert the results of lisp evaluation in the consequent expression. To enable both uses, the result of a :LISP at top level is ignored (not treated as a derived expression to be added to the data dnet); while the result of a :lisp :lisp embedded in an expression is included in that expression when it is indexed as a new datum. (:BIND <var> <expr>) - Variables in <expr> are bound as for :LISP, <expr> is evaluated, and the result is bound to <var>, which must be a variable. Useful in antecedent to define variables used in consequent, eg. to prevent use of :lisp in consequent which needs to be matched to for backchaining. (An example of this will be given, see "OHMS-LAW" and "OHMS-LAWLESS".) (:DELETE <expr>) - Variables in <expr> are bound, and the expression is deleted from the active data base. (Any truth maintenance activities will be up to the application, perhaps using the DELEXPR-HOOK of the DNET.) Applies only to forward rules. The slots of an SM rule object are as follows: ANTECEDENT: A list, with :AND, :SEQ, :LISP and :BIND, possibly nested where appropriate. Factors after factoring :OR must be lists. CONSEQUENT: A list, :AND and :SEQ may be embedded, :LISP OK but :BIND and :OR not interpreted. DIRECTIONS: One of :FORWARD :FORWARD-UNIQUE, :BACKWARD, or :BOTH: the way the rule is used. See :comments on the slot for details. INTERNED-IN: A list of DNETs the rule is stored in. ADD-RULE updates it. INFO: Association list of keywords to info needed by your code. COMMENTS: String -- intent of the rule, etc. Now for examples. The simplest kind of rule has no logical combiners or escapes to lisp, and can be used both forwards and backwards to deduce new data. These rules are essentially subclass statements: (defvariable x) (rule sad-fact :antecedent (human ?:x) :consequent (mortal ?:x)) This next rule illustrates several things ... (defvariable r) (rule run-away :antecedent (:and (in (room ?:r) self) (burning (room ?:r))) :consequent (:lisp (run-like-hell-from-room ?:r)) :directions :forward) 1. During forward reasoning, :AND is interpreted specially (not matched) by seeing if both the enclosed forms match some datum in the DB with consistent variable bindings. 2. When :LISP is seen, the interpeter lambda-binds ?:r, then calls EVAL. 3. The rule need only be stored in the forward form, as we never backchain on :LISP consequents. 4. Notice I have ROOM wrapped around most occurances of ?:r. While working out some detailed examples, I found that sometimes I wanted rules with the same antecedent to apply to different TYPES of objects, yielding different results according to the type. For example, you may use a different procedure to escape a burning ship. One solution is to require that all references to variables, in both rules and data, are enclosed in a predication of the type the variable is restricted to. (I don't do this for :LISP because the evaluator doesn't need to mess with it.) The drawback is if a rule applies to multiple types, you have to generate a different one for each type (perhaps automatically, by inheritance). To illustrate factoring, the following rule is parsed into six rules: (rule says-a-lot :antecedent (:or (whale ?:x) (man ?:x)) :consequent (:and (mortal ?:x) (mammal ?:x))) Internally to DNET, it is stored as these forward rules: (whale ?:x) => (mortal ?:x) (whale ?:x) => (mammal ?:x) (man ?:x) => (mortal ?:x) (man ?:x) => (mammal ?:x) and these backwards rules: (mortal ?:x) => (:or (whale ?:x) (man ?:x)) (mammal ?:x) => (:or (whale ?:x) (man ?:x)) If you read the Programmer's Introduction, you'll find out why this involves only 4 indexed expressions, and how the expressions on the right are stored in the EXPR-INFO of these indexed expressions. The antecedents for back- chaining rules are not parsed for efficiency reasons (the order of components of :AND, :SEQ, and :OR contains control information about what to try first, and factoring produces redundant expressions, forcing the backchainer to repeat work previously done). To summarize discussion in the programmer's introduction on the effect of using :AND and :OR in the antecedent and consequent on forward and backward rules: 1. There is NO DIFFERENCE in logical behavior between using :AND (or :SEQ) in the CONSEQUENT of a single rule and writing two rules, whether reasoning FORWARD OR BACK. 2. There is NO DIFFERENCE to FORWARD chaining whether you write one :OR ANTECEDENT or two rules. 3. There is NO DIFFERENCE to BACKWARD chaining whether you write one :OR ANTECEDENT or two rules. 4. There is IS A DIFFERENCE in using :AND in the ANTECEDENT, since some rules are not expressible without it. Forward chaining cannot match to an :AND antecedent without special interpretation to see if the conjunct holds. For this reason, there are two forward chaining functions. One interpets :AND over a data base, the other triggers off a single datum. 5. :OR in the CONSEQUENT isn't allowed (well, you can do it but the code ignores it). We restrict the expressiveness of the language in this way for tractability reasons. (:NOT is not used for similar reasons.) 6. Exceptions to the above are as follows: a. When analyzing SUPPORT trees, the form of the tree will differ depending on the above choices, though the logical support is the same. Also, :AND permits :record-failure to try conjuncts subsequent to a failing one, while :SEQ does not. b. If there are :LISP side effects, the difference in rule order versus clause order may result in a difference in side effects in #'s 1, 2 and 3. c. Nested :ANDs and :ORs in the antecedent of backwards rules may be more efficient than the separate rule representation, though logically equivalent, because factoring results in redundant expressions which causes the backchainer to do redundant processing. Here is an example of :BIND, and how it is better than :LISP in some cases. Note also the use of the (<type> <variable>) technique to restrict the applicability of a rule. (defvariable r1) (defvariable p1) (defvariable p2) (defvariable v) (defvariable a) (rule ohms-law :antecedent (:and (ports (resistor ?:r1) (port ?:p1) (port ?:p2)) (resistance (resistor ?:r1) (ohms ?:r)) (voltage-across (port ?:p1) (port ?:p2) (volts ?:v)) (:bind ?:a (/ ?:r ?:v))) :consequent (current-at (port ?:p2) (amps ?:a))) :BIND makes it possible to use this rule in both directions, because it defines a variable in the antecedent so it can be used in the consequent without a messy :LISP. If I had written: (rule ohms-lawless :antecedent (:and (ports (resistor ?:r1) (port ?:p1) (port ?:p2)) (resistance (resistor ?:r1) (ohms ?:r)) (voltage-across (port ?:p1) (port ?:p2) (volts ?:v))) :consequent (current-at (port ?:p2) (amps (:lisp ?:a (/ ?:r ?:v))))) the consequent would contain an ugly :LISP thing that cannot be matched to in back chaining. The backchainer will know how to deal with :BIND in an antecedent, since it interprets each of the conjuncts one by one, and does not attempt to match to :BIND. DNET and RULEs: The code is written so that you may save a DNET of rules, reload it in a new session without loading the SM RULE objects stored in it, and things will still work. This saves space when running versions of the system where you don't expect to edit the rules. The code for defining RULEs and loading them into a DNET is separated from the inferencing code. Both share a data definitions file. This allows separate loading, saving more space. See also the Programmer's Introduction for an idea of how rules are stored and processed. --------------------------------------------------------------------------- SUPPORT TREES The SUPPORT function takes a pattern as argument, and returns a tree of all ways in which back chaining supports the pattern. It has a :RECORD-FAILURE &key arg, which if T forces it to record failures as well as successes. Otherwise NIL is returned on failure. The TRJ-NODE structure has CLAIM, MODALITY, & SUPPORT slots. * CLAIM is a pattern (may have variables), or an :AND or :OR expression. * MODALITY says whether the CLAIM is supported, and with what modality. (Right now we are using just "true" and "false", which I'll represent as :SUPPORTED and :UNSUPPORTED.) We need this slot because a non-NIL SUPPORT does not necessarily mean failure when :RECORD-FAILURE is T. * SUPPORT is a list of TRJ-ARC structures. If NIL, this indicates failure to support the CLAIM, but if non-NIL and :RECORD-FAILURE is T, you have to look at MODALITY to tell. This list is an implicit disjunction: each TRJ-ARC points to a subtree which is an alternate way to support the goal. A TRJ-ARC consists of WARRANT, GROUNDS, and BINDINGS. * WARRANT is one of :ASSERTED, :AND, :SEQ, :OR, or the name of a rule. :ASSERTED means the CLAIM is supported by being found in the data base; :AND, :SEQ, and :OR mean this support structure decomposes the indicated operator. <Rule> means the arc is sanctioned by the indicated rule. * GROUNDS and BINDINGS are as follows: - CLAIM of (:AND <C1> ... <Cn>) gets TRJ-ARCs of form: #S(TRJ-ARC WARRANT :AND GROUNDS (<support-for-C1> ... <support-for-Cn>) BINDINGS <bindings>) where <support-for-Ci> are TRJ-NODEs, and in a given list each <support-for-Ci> unifies with its corresponding <Ci> under the same <bindings>. Since the bindings must be consistent, yet there may be multiple ways for them to be consistent, an :AND may produce multiple arcs. - CLAIM of (:SEQ <C1> ... <Cn>) gets TRJ-ARCs similar to :AND, of form: #S(TRJ-ARC WARRANT :SEQ GROUNDS (<support-for-C1> ... <support-for-Ck>) BINDINGS <bindings>) where <support-for-Ck> is for the last conjunct that succeeded (k=n if :record-failure nil, since otherwise the arc is not recorded). - CLAIM of (:OR <D1> ... <Dn>) gets TRJ-ARCs of form: #S(TRJ-ARC WARRANT :OR GROUNDS (<support-for-D1> ... <support-for-Dn>) BINDINGS (<bindings1> ... <bindingsn>)) If record-failure is NIL, only successful Di are on the list. The bindings list corresponds to the grounds list. Since bindings do not have to be coordinated across disjuncts, there is only one TRJ-ARC for an :OR node. Why record this at all? It seems like a NO-OP, and we could lift the disjunction in GROUNDS up into the implicitly disjunctive SUPPORT slot of the TRJ-NODE that contains this. My guess is that we want to be able to tell what disjunctions are due to alternate ways to match, and what due to a specified :OR, because it will affect how we explain and justify the results. When someone writes :OR, they are saying something about the semantics of the concept, not just that the concept may apply to multiple entities (i.e. not just that a variable binds to multiple objects). - CLAIM of <pattern> gets TRJ-ARCs of one of these forms: #S(TRJ-ARC WARRANT <rule-name> GROUNDS <support-node> BINDINGS <bindings>) where <bindings> unifies <pattern> with the consequent of <rule-name>; @@@ UNIFIES? #S(TRJ-ARC WARRANT :ASSERTED GROUNDS <expression> BINDINGS <bindings>) where <bindings> unifies <pattern> with <expression> (which has no variables). - :LISP and :BIND are recorded by ... ?@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ WHEN :RECORD-FAILURE is T: We record unsupported subgoals so analysis may be done concerning why a CLAIM may be UNsupported. There are some decisions to make about what to record. If a subgoal is supported, do I also record ways in which it failed to be supported? We decided not to do this. In general, we are avoiding any record of failure which requires that the pattern matching facilities of DNET be reimplemented to keep track of failure. That matching is automatic, and we won't record failure at that granularity. Furthermore, to do so would make everything in a database a potential failure. We want in principle to record only the failure of those subgoals having some conceptually useful granularity. However there is still some decision to be made here. Suppose the top level CLAIM fails. Do I always return: #S(TRJ-NODE CLAIM <goal> MODALITY :UNSUPPORTED SUPPORT NIL)? This doesn't tell us any thing; might as well return NIL. So how can we give more info without having to pick apart how the pattern matcher failed? - :AND and :OR goals are always decomposed, even if they failed. Their recursive <trj-node>s tell us something about what happened. - :SEQ stops at the first failure (it was implemented for this purpose). - Patterns that a rule matched to have a subtree for the rule to show how the antecedent failed. - Patterns that failed without a rule match are the terminals. They look like: #S(TRJ-NODE CLAIM <pattern> SUPPORT NIL) Importantly, we RETAIN ANY SUCCESSFUL SUBGOAL TREES; otherwise this entire tree would only be telling us how the :ANDs and :ORs are nested (which we already know), and what rules failed. We want to also know how close the rules got. |# ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; PROGRAMMER'S INTRODUCTION ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; #| This section motivates how DNET is used to support rules. The actual code is more elaborate than the examples below, but this will give you an initial idea of the approach, to enable you to read the actual code more easily. If you have loaded DNET, you can evaluate the expressions given as examples to see the examples run. By way of review of what the documentation in the DNET package will tell you: - DNET can store any expression consisting of UN-DOTTED lists and atoms. - A variable is a symbol in the ? package. Create them with: (defvariable x). - Store an expression with: (indexpr <expr> <dnet>). - Associate information with it with: (expr-info <expr> <dnet>). - Retrieve expressions matching a pattern with (match-pattern <pat> <dnet>). - Retrieve patterns matching an expression with: (match-expression <expr> <dnet>). - Retrieve patterns matching a pattern with: (match <pat> <dnet>). - We make a rule-base dnet with (make-dnet <name-of-rule-base>). --------------------------------------------------------------------------- INDEXING OF RULES: See the documentation of the SM definition of a RULE (in this file) for the current syntax of a rule. SM RULE objects are "loaded" into a rule-base by indexing into the DNET which constitutes that rule base. The approach taken stores forward and backward forms of the rules separately. This lets you control which way a rule is to be used, and allows the use of far more efficient algorithms for matching. Rules are also parsed before storing to factor out any :OR's in the antecedent or :AND's in the consequent. (:SEQ is also factored in consequents, since the order is preserved.) The forward form is stored by indexing into the DNET with the antecedent, and storing in its INFO a list of "rule records" containing the consequents reached by that antecedent. The backwards form does the reverse. Antecedents and consequents indexed in the DNET are distinguished from each other by consing the keys :ANTECEDENT and :CONSEQUENT onto them, respectively. This ensures that an antecedent doesn't get retrieved when we are matching to find a consequent, and vice versa. Rule records in the INFO lists are tagged by the rule that placed them there. This lets us tag each deduction with the responsible rule, and to merge redundant parts of rules without loosing the ability to delete only one of them later on. Again, if you have DNET loaded, you may evaluate the uncommented forms as we go. To get things started, make a data and a rules DNET, and define a variable: (in-package :RULE) (make-dnet :data) (make-dnet :rules) (defvariable x) Our (bogus) example rules will be: (rule r1 :antecedent (:and (professional ?:x) (works-at-home ?:x)) :consequent (applicable home-office-deduction ?:x)) (rule r2 :antecedent (:or (doctor ?:x) (lawyer ?:x)) :consequent (professional ?:x)) Factoring has no real effect on R1. Its forward form is stored by code that has essentially the following effect: (indexpr (cons :antecedent '(:and (professional ?:x) (works-at-home ?:x))) :rules (list (cons 'r1 '(applicable home-office-deduction ?:x)))) The backwards form is stored by: (indexpr (cons :consequent '(applicable home-office-deduction ?:x)) :rules (list (cons 'r1 '(:and (professional ?:x) (works-at-home ?:x))))) Factoring of R2 yields an implicit disjunction of antecedents: ; ((doctor ?:x) (lawyer ?:x)) Factoring is not always this trivial: it can factor out embedded :OR's too. For example, an antecedent of (:and (bar ?:x) (:or (foo ?:x) (fie ?:x))) factors to: ; ((:and (bar ?:x) (foo ?:x)) (:and (bar ?:x) (fie ?:x))). Now R2 is stored by: (indexpr (cons :antecedent '(doctor ?:x)) :rules (list (cons 'r2 '(professional ?:x)))) (indexpr (cons :antecedent '(lawyer ?:x)) :rules (list (cons 'r2 '(professional ?:x)))) (indexpr (cons :consequent '(professional ?:x)) :rules (list (cons 'r2 '(:or (doctor ?:x) (lawyer ?:x))))) Note we associated the consequent to the unparsed form of the antecedent. This is because the :ORs of an antecedent may contain control information, and it was determined that parsing forces backchaining to do redundant processing. Now, look at what is indexed in your rules DNET with: (mapcar #'(lambda (e) (format t "~%~S => ~S" e (expr-info e :rules))) (all-expressions :rules)) --------------------------------------------------------------------------- FORWARD REASONING: There are two kinds of forward reasoning supported by separate functions. In one, INFER-FROM-DATUM, we see if any rules trigger from a single datum in isolation. In the other, FORWARD-CHAIN, we provide a DNET of data and a DNET of rules, and allow forward reasoning to run on any rules which match any combination of data. An argument controls whether to run once or run until quiescence (no new data added). To illustrate INFER-FROM-DATUM triggering off of an isolated new datum, assume we have just found out that (doctor joe): (indexpr '(doctor joe) :data) and we want to make whatever immediate inferences are possible. In effect, we find the applicable forward rules as follows: (match-expression (cons :antecedent '(doctor joe)) :rules) ==> ((:ANTECEDENT DOCTOR ?:X)) (((?:X . JOE))) Two values are returned: a list of rule antecedents matching the new datum, and a list of binding sets corresponding to the list of rules. Since the results are non-NIL we know we have at least one rule. For each rule in the first list (there is only one), we have to retrieve its EXPR-INFO, substitute the bindings specified in the second list, yielding the rule's conclusion. Let's look at that in two parts: (expr-info '(:antecedent doctor ?:x) :rules) ==> ((R2 PROFESSIONAL ?:X)) We get back a list of all conclusions which the antecedent sanctions. Here we have only one, labeled by the rule which provided it. If there were more than one, they could have come from an :AND in the consequent of the rule, and/or from other rules with the same antecedent. To process all the conclusions, we map across the expr-info, taking the CDR to knock off the rule names, and substitute for the variable (the actual code uses a RULE-RECORD abstraction instead of CDR, etc.): (mapcar #'(lambda (c) (substitute-bindings '((?:x . joe)) (cdr c))) (expr-info '(:antecedent doctor ?:X) :rules)) ==> ((PROFESSIONAL JOE)) The result is an implicit conjunction of new data. FORWARD-CHAIN now INDEXPRs each into a database of data: (indexpr '(professional joe) :data) You can see the current contents of :data with: (all-expressions :data) The other kind of forward reasoning, FORWARD-CHAIN, tries to apply a rule base to an entire DNET of data. Unlike INFER-FROM-DATUM, the chain version is capable of interpreting :AND in the antecedent. This can only be done when the entire data DNET is being operated on, because you have to try matching to all combinations of data to see if an :AND succeeds, not just an isolated added datum. FORWARD-CHAIN iterates over all the forward rules, attempting to match each to the data. An internal form of MATCH-PATTERN is used instead of MATCH-EXPRESSION, because we are matching a pattern to a DNET of variable-less expressions. If the antecedent being tested has no :AND, the code is in effect: (match-pattern (cdr '(:antecedent doctor ?:x)) :data) ==> ((DOCTOR JOE)) (((?:X . JOE))) This tells us that one datum matched to the rule, and tells us the bindings we need to substitute into the rule's consequent to get the conclusion. The remainder is similar to the above example. If an :AND is seen, FORWARD-CHAIN applies the above process of matching to the data to each conjunct in turn, aborting if any fails to produce a result. The bindings of the results must agree, so those data that match but don't agree in bindings are eliminated. Bindings used for matching each conjunct are substituted into subsequent conjuncts before proceeding. If multiple data match a conjunct, the :AND processing splits for each way of matching, with different bindings substituted for each. If a :LISP or :BIND form is encountered, it is processed as described in the User's Introduction, by binding the variables and evaluating. ---------------------------------------------------------------------------- BACKWARD REASONING: First let's reset the data base, so we can use the same example again: (make-dnet :data) Here we have a goal and want to base it in data. The rule representation is similar to above, and won't be spelled out in detail here. Matching is more complicated: I first describe backchaining as if goals never have variables, then deal with that problem. (indexpr '(works-at-home joe) :data) (indexpr '(doctor joe) :data) Say our goal is (applicable home-office-deduction joe). Since the goal has no special operator, see if any rules conclude the goal: (match-expression (cons :consequent '(applicable home-office-deduction joe)) :rules) ==> ((:CONSEQUENT APPLICABLE HOME-OFFICE-DEDUCTION ?:X)) (((?:X . JOE))) The INFO associated with this is an implicitly disjunctive list of rule-records resulting from :OR-factoring the antecedents of all the rules that have this consequent. (expr-info '(:consequent applicable home-office-deduction ?:x) :rules) ==> ((R1 :AND (PROFESSIONAL ?:X) (WORKS-AT-HOME ?:X))) Substituting variables into the single rule-record returned above gives the subgoal for backchaining: (substitute-bindings '((?:x . joe)) (rest (first (expr-info '(:consequent applicable home-office-deduction ?:x) :rules)))) ==> (:AND (PROFESSIONAL JOE) (WORKS-AT-HOME JOE)) A backchainer which recognizes :AND will know to work on the two goals (professional joe) and (works-at-home joe) separately, trying to achieve both. It would first check the :data data base to see if they are present. If not, it would apply the present process recursively, trying to find a rule consequent that matches the subgoal. For example: (match-pattern '(works-at-home joe) :data) ==> ((WORKS-AT-HOME JOE)) (NIL) But (professional joe) is not found, and requires subgoaling: (match-pattern '(professional joe) :data) ==> NIL NIL Recall (rule (doctor ?:x) (professional ?:x)) is in :rules and (doctor joe) in :data. Then it is just a reapplication of what you've seen: (match-expression (cons :consequent '(professional joe)) :rules) ==>((:CONSEQUENT PROFESSIONAL ?:X)) (((?:X . JOE))) (substitute-bindings '((?:x . joe)) (rest (first (expr-info '(:consequent professional ?:X) :rules)))) ==> (:OR (DOCTOR JOE) (LAWYER JOE)) (match-pattern '(doctor joe) :data) ==> ((DOCTOR JOE)) (NIL) ------------ Elaboration: This simple picture is complicated primarily by (a) the presence of variables in goals, (b) maintaining consistency of bindings; and (c) splitting for multiple ways to satisfy a goal. Variables in goals mean we have to use MATCH instead of MATCH-EXPRESSION when retrieving rules. Bindings may work in both directions. For example, first add a rule that uses two variables so we can show bindings working both ways: (defvariable y) (defvariable j) (indexpr '(:consequent loves ?:x ?:y) :rules '((R-love :or (loves ?:y ?:x) (unhappy ?:x)))) Assume our goal is (loves Mary ?:j). Then to find applicable rules: (match '(:consequent loves Mary ?:j) :rules) ==> ((:CONSEQUENT LOVES ?:X ?:Y)) (((?:J . ?:Y))) (((?:X . MARY))) Since the main goal has a variable in it, part of the "answer" we expect from the backchainer is a binding for this variable. The first set of bindings, ((?:j . ?:y)) tells us what this answer is. Unfortunately the answer is not immediately available: we have to backchain to find an answer for ?:y to know the answer for ?:x. Before backchaining, the second set of bindings has to be substituted into the antecedent, to get the more specific (appropriately bound) subgoal: (substitute-bindings '((?:x . mary)) (rest (first (expr-info '(:consequent loves ?:x ?:y) :rules)))) ==> (:OR (LOVES ?:Y MARY) (UNHAPPY MARY)) The "answer" returned by recursive processing on a subgoal will include binding of any variables in the subgoal. To get the bindings for the main goal, we have to substitute bindings for the subgoal into the CDRs of bindings for the goal. This replaces bindings of variables to variables with a more useful binding. For example, assume subgoaling on (loves ?:y mary) returns a result of ((?:y . joe)). Then the answer is got by: (substitute-bindings '((?:y . joe)) '((?:j . ?:y))) ==> ((?:J . JOE)) (The actual code only allows substitution into the CDR, to avoid accidental replacement of ?:j.) The backchainer returns this binding set as the second value of its answer. The first value is constructed by substituting this binding set into the original goal expression: (substitute-bindings '((?:j . joe)) '(loves Mary ?:j)) ==> (LOVES MARY JOE) Consistency of bindings across conjuncts is maintained by substituting in the bindings which satisfy a conjunct into all subsequent conjuncts. Then they become more specific subgoals which are implicitly consistent with those already satisifed. All processing works with sets of binding sets, representing alternate ways to support, rather than with a single binding set as in the examples. If a goal matches a data base in multiple ways, then all subsequent processing which depends on use of these bindings (including iteration across conjuncts) splits for each binding set. The programmer is advised to read RETRIEVE before trying to understand SUPPORT. ---------------------------------------------------------------------------- PARTITIONED RULE SETS: It is a simple matter to partition the rules, eg: (make-dnet :control-rules) (make-dnet :legal-rules) (make-dnet :term-definition-rules) ... Then the interpreter would access the appropriate dnet. A future feature of DNET will be the ability to define child dnets, which inherit all expressions from their parents but add some own of their own. This is surprizingly straightforward, and enables hypothetical reasoning by extending data bases as well. ---------------------------------------------------------------------------- RATIONALE for STORING THE RULE TWICE: The above approach is efficient, and allows you to specify whether a rule is forward, backward, or both. However, perhaps you want to use the save-dnet facility to create editable files which don't have the rules represented two different ways. There are some problems, though. We have to account for the presence of the entire expression in constructing what to match to, but the stored rule expression contains variables, and so does the retrieval cue. This means we have to use MATCH, which does full unification. It slows things down enough to make the more complex dual- direction implementation worthwhile. To allow us to edit the rules in their original form, I have defined them as SM objects. ---------------------------------------------------------------------------- RATIONALE for FACTORING AND INDEXING RULES: While an :AND in the antecedent serves a real purpose, :AND in the consequent and :OR in the antecedent are only for convenience, in writing one rule for what would otherwise be multiple but similar rules. That is: - :AND in the consequent means you can use the antecedent to conclude any of the conjuncts in the consequent. A separate rule could have been written for each. - :OR in the antecedent means you can conclude the consequent if any of the antecedent conditions obtains. A separate rule could have been written for each antecedent conditions. - :SEQ cannot be factored, since it serves control purposes. The purpose of parsing is to split these composite rules into their components, so that the matcher does not have to deal with :AND and :OR. We INDEXPR parsed antecedents and consequents, and map them to their counterpart. But what about the counterpart mapped to? Is it ever necessary to parse it too? To answer this question, consider: :FORWARD rules may contain :AND or :SEQ in the consequent. When a forward rule fires, we add all the data derived. Hence, to save parsing at run-time, we should store the :AND-factored form of the consequent in the expr-info mapped to by the antecedent. Also, it is concievable that in a poorly coordinated rule base, a different rule may use the same :OR-factored antecedent but draw different conclusions. We want to store the union of all :AND-factored conclusions drawn by rules sharing the same :OR-factored antecedents. The solution is to map each :OR-factored antecedent to an implicit conjunction of :AND-factored consequents. :BACKWARD rules may contain :AND or :OR in the antecedent. Factoring may produce inefficient backchaining. For example: (:and (foo x) (fie x) (:or (fum x) (bar x))) => ((:and (foo x) (fie x) (fum x)) (:and (foo x) (fie x) (bar x))) In the parsed form, the backchainer will try foo and fie twice each. This suggests making the info a list of rule-records containting the rule name and the unfactored antecedent. If multiple rules have the same consequent, we store a rule record for each on this list, with implicit disjunction. IN SUMMARY: INDEXPR'ed ANTECEDENTS are :or-factored, and map to an implicit conjunct list of :and-factored consequents (each of which should not contain :or's, as they are not interpreted). All the conjuncts are asserted when forward chaining. INDEXPR'ed CONSEQUENTS are :and-factored, and map to an implicit disjunct list of unfactored antecedents (each of which may contain :ands and :ors). The backchainer succeeds if it can support any one of them. --------------------------------------------------------------------------- BACKCHAINING SPECIFICS The current implementation of SUPPORT finds ALL ways a goal can be supported, and returns a tree of TRACE-NODEs representing this support. All calling except a top level user function is done using trace-nodes, and all returned results are trace-nodes. In the future, one will be able to specify the extent to which support should be sought (e.g. stop after first proven), and get back a tree of trace-nodes with unexplored alternate ways to support the goal. At the same time, the backchainer will be reimplemented to be able to take one of these partial trees and complete it. This greatly simplifies the implementation of :AND and :OR. No backtracking is required, as we are simply searching to find all possible consistent bound support trees. Both :AND and :OR invoke recursive processing on all their constituents (short-circuiting only :AND if :record-failure is nil), the difference being that bindings must be consistent across :AND calls, and their results are merged into one support subtree, whereas :OR bindings are in distinct worlds, and consititute alternate subtrees. For example, say we have a data base: {(foo A), (fie B), (fum B)} and a goal: (:AND (:OR (foo ?:x) (fie ?:x)) (fum ?:x)) If we did not explore all alternatives, here's how we run into the backtracking problem with short circuiting [the actual code calls and returns with trace-nodes]: Goal: (:AND (:OR (foo ?:x) (fie ?:x)) (fum ?:x)); Bindings: () Calls Goal: (:OR (foo ?:x) (fie ?:x)); Bindings () Calls (foo ?:x); Bindings () Returns Success with Bindings (((?:x . A))) Returns Success with Bindings (((?:x . A))) Calls Goal: (fum ?:x); Bindings: (((?:x . A))) Returns Failure [since (fum B) yields inconsistent bindings] Now we have to backtrack to pursue the other :OR option. We have to know that (fie ?:x) is the next thing to try -- to not restart at the beginning of the :OR. The way to do this is to NOT call an :OR-processor anew with the fresh :OR expression -- we have to have kept track of where we were in the :OR, so when we backtrack we know this is a choice point with remaining options to explore. The full search approach interprets the :OR by splitting into alternate subtrees: Goal: (:AND (:OR (foo ?:x) (fie ?:x)) (fum ?:x)); Bindings: () Calls Goal: (:OR (foo ?:x) (fie ?:x)); Bindings () Calls (foo ?:x); Bindings () Returns Success with Bindings (((?:x . A))) Calls (fie ?:x); Bindings () [since :OR] Returns Success with Bindings (((?:x . B))) Calls Goal: (fum ?:x); Bindings: (((?:x . A)) ((?:x . B))) [Two alternate sutrees are represented by two binding sets.] Returns Success with Bindings (((?:x . B))) [Inconsistent set filtered] Returns Success with Bindings (((?:x . B))) --------------------------------------------------------------------------- THOUGHTS ON UNIQUE BINDINGS Backchaining can run into an infinite loop when the consequent of a rule matches one of its antecedents, or this condition obtains between a set of rule in a circular manner. Example: (RULE VOLTAGE-PROPAGATION :ANTECEDENT (:and (voltage-across (port ?:p1) (port ?:p2) (volts ?:v)) (connected (port ?:p1) (port ?:p3)) (connected (port ?:p2) (port ?:p4))) :CONSEQUENT (voltage-across (port ?:p3) (port ?:p4) (volts ?:v))) (voltage-across (port ?:p3) (port ?:p4) (volts ?:v)) Matches (voltage-across (port ?:p1) (port ?:p2) (volts ?:v)), and the rule invokes an infinite loop of back chaining. One solution is to keep track of what bindings are currently active for each rule, and disallow rebinding each rule with the same bindings during the backchaining call. This is the solution taken here. Variables are uniquified for each rule, so we only have to keep track of bindings for variables without indexing them by rule. A PSEUDO-solution is to write such rules in a different order, hoping to use the other conjuncts to constrain the bindings of the variables in such a way that the offending conjunct cannot unify with the consequent of the same rule. This does not always work because (1) two rules may play off of each other; or even (2) one rule, such as the above, may play off against itself by alternating bindings (the voltage is "propagated" back and forth between two sets of ports). Both of these have occured in my empirical tests. Forward rules have a related problem. A :LISP consequent forward rule could fire more than once in a given forward chaining invocation, and the number of times is unpredictable (depends on how many times other rules are able to add new data to the data base). The designation :FORWARD-UNIQUE or :BOTH-UNIQUE indicates that a rule can not be invoked forward on the same bindings twice. This is not a real problem for datum adding forward rules because they are only allowed to add or justify a given datum once, but for efficiency the user may still want to designate such rules as :forward-unique. Note the differences: a :FORWARD-UNIQUE prohibition is specified by the user for specific rules, and is in effect across calls to the forward chainer (until FORGET-BINDINGS is invoked); while the backchaining unique rebinding requirement is automatically applied to all backchaining rules, and is in effect only for the duration of a backchaining session. @@@ Problems etc.: Forward :LISP rules fire currently as long as datum rules are firing, but no more. Question is whether we want lisp rules that keep going until THEY fail to fire. This would be better than having the number of times a :lisp rule fires be dependent on what other (expression adding) rules are present. Question: Do we want to be able to specify forward unique (a) across sessions, (b) during a session? Latter may be needed for :LISP rules which are not to repeat during a session, but should run each session. |# ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (in-package :RULE) ;;; Basics. (require :DIALOGUE) (require :SM ) (require :DNET ) (require :MISC ) (require :MAPPINGS) ;;; These definitions are always required. (require :Rule-Defs #+:CCL "ccl;MODULES:RULES:rule-defs") ;;; This is only needed when editing SM RULE objects and building rule ;;; dnets. Already-constructed dnets may be loaded without the SM ;;; RULE type being defined. (require :Rule-Build #+:CCL "ccl;MODULES:RULES:rule-build") ;;; Graphing stuff etc. is loaded if in Allegro. #+:CCL (require :SMEDIT ) #+:CCL (require :DNET-Browser ) #+:CCL (require :GRAPHER ) #+:CCL (require :Rule-Browser #+:CCL "ccl;MODULES:RULES:rule-browser") ;;; Forward and backward reasoning may be loaded separately. (require :Rule-Forward #+:CCL "ccl;MODULES:RULES:rule-forward") (require :Rule-Back #+:CCL "ccl;MODULES:RULES:rule-back") ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (provide :RULES) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; the end.